package 中等.其他;

/**
 * 给你一个整数数组 nums 和一个整数 k ，请你统计并返回
 * nums 的子数组中元素的最大公因数等于 k 的子数组数目。
 * 子数组 是数组中一个连续的非空序列。
 * 数组的最大公因数 是能整除数组中所有元素的最大整数。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/number-of-subarrays-with-gcd-equal-to-k
 */
public class 最大公因数等于K的子数组数目_2447 {

    public static void main(String[] args) {

        System.out.println(subarrayGCD(new int[]{3, 12, 9, 6}, 3));

    }

    public static int subarrayGCD(int[] nums, int k) {
        int count = 0;

        if (nums[0] == k) {
            count++;
        }
        for (int i = 1; i < nums.length; i++) {
            int left = i;
            int curGcd = getGcd(nums[left], nums[i]);
            // 性质：如果a和b的最大公约数为k1,c和k1的最大公约数为k2，那么a,b,c的最大公约数为k2
            while (left >= 0 && curGcd >= k) {
                if (curGcd == k) {
                    count++;
                }
                left--;
                if (left >= 0) {
                    curGcd = gcd(nums[left], curGcd);
                }
            }
        }

        return count;
    }

    // 更相减损法
    private static int getGcd(int x, int y) {
        if (x == y) {
            return x;
        }
        if (x == 0 || y == 0) {
            return 0;
        }
        int twoSqrt = 1;
        while (x % 2 == 0 && y % 2 == 0) {
            x /= 2;
            y /= 2;
            twoSqrt *= 2;
        }

        while (x > 0 && y > 0) {
            int min = Math.min(x, y);
            int max = Math.max(x, y);

            int diff = max - min;
            if (min == diff) {
                return twoSqrt * diff;
            }
            x = diff;
            y = min;
        }
        return 0;
    }

    // 辗转相除法
    private static int gcd(int a, int b) {
        return b == 0 ? a : gcd(b, a % b);
    }

}
